package org.example.lc;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.*;

/**
 * 爬楼梯
 *  1 1,2
 *  2 1,2
 *
 *  1 1 1 = n ?
 *  2 1 2 = n ?
 *        2 2
 *        最多走n步
 *         1
 */
public class p70 {
//    int total;
    int[] mem;
    public int can(int nowStep,int previousStepCount,int n) {

        if(nowStep>0) {
            if(mem[nowStep]!=-1) {
                return mem[nowStep];
            }
                int a1 = can(nowStep - 1, 1, n);
                int a2 = can(nowStep - 2, 2, n);
                mem[nowStep] = a1+a2;
                return a1+a2;
        }
        else if(nowStep==0){
//            System.out.println("find");
//            total+=1;
            return 1;
        }
        else {
            return 0;
        }
    }
    public int climbStairs(int n) {
//        total = 0;
        mem = new int[n+1];
        Arrays.fill(mem,-1);
        int result = can(n,0,n);
//        System.out.println("result:"+result);
//        can(n-1,1,n);
//        System.out.println(Arrays.toString(mem));
        return result;
    }
    @Test
    public void d1() {
        assertEquals(2,climbStairs(2));

    }
    @Test
    public void d2() {
        assertEquals(3,climbStairs(44));

        //1134903170
    }
}
